﻿#ifndef __GRAPHCONNECTIVED__
#define __GRAPHCONNECTIVED__
#include <iostream>
#define MAX_NODE_NUM 100
int father[MAX_NODE_NUM];
void Initialize(){
	for(int i = 0; i < MAX_NODE_NUM; ++i)
		father[i] = i;
}

//快速查找解法
void QuickSearchMethod(){
	Initialize();
	int p , q;
	for(;;){
		std::cin >> p >> q;
		if(father[p] == father[q]) continue;
		std::cout << p << " -- " << q << std::endl;
		for(int i = 0; i < MAX_NODE_NUM; ++i)
			if(father[i] == father[q]) 
				father[i] = father[p];
	}
}

//快速合并解法
void QuickMergeMethod(){
	Initialize();
	int p, q;
	for(;;){
		std::cin >> p >> q;
		int i, j;
		for(i = p; i != father[i]; i = father[i]);
		for(j = q; j != father[j]; j = father[j]);
		if(i == j) continue;
		father[j] = i;
		std::cout << p << " -- " << q;
	}
}

int rank[MAX_NODE_NUM];
void NewInitialize(){
	for(int i = 0; i < MAX_NODE_NUM; ++i){
		rank[i] = 1;
		father[i] = i;
	}
}
//带权的快速合并解法
void QuickMergeWithRankMethod(){
	NewInitialize();
	int p, q;
	for(;;){
		std::cin >> p >> q;
		int i, j;
		for(i = p; i != father[i] ; i = father[i]);
		for(j = q; j != father[j] ; j = father[j]);
		if(i == j) continue;

		if(rank[i] < rank[j]){
			father[i] = j;
			rank[j] += rank[i];
		}else{
			father[j] = i;
			rank[i] += rank[j];
		}

		std::cout << p <<" -- " << q << std::endl;
	}
}

//等分路径压缩的带权快速合并解法
void PathCompressionAndQuickMergeWithRankMethod(){
	NewInitialize();
	int p, q;
	for(;;){
		std::cin >> p >> q;
		int i, j;
		for(i = p; i != father[i] ; i = father[father[i]]);
		for(j = q; j != father[j] ; j = father[father[j]]);

		if(i == j) continue;

		if(rank[i] < rank[j]){
			father[i] = j;
			rank[j] += rank[i];
		}else{
			father[j] = i;
			rank[i] += rank[j];
		}

		std::cout << p << " -- " << q << std::endl;
	}
}
#endif